# -*- coding: utf-8 -*-


# 插入排序-直接插入
# arr=[3,5,4,9,8,7]
def insert_sort(array):
    for i in range(1, len(array)):
        temp = array[i]
        j = i - 1
        while j > -1 and array[j] > temp:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = temp
    return array


# 二分折半直接插入
def half_insert_sort(array):
    for i in range(1, len(array)):
        left = 0
        right = i - 1
        temp = array[i]
        while left <= right:
            mid = int((left + right) / 2)
            if array[mid] < temp:
                left = mid + 1
            else:
                right = mid - 1
        j = i - 1
        while j >= left:
            arr[j + 1] = arr[j]
            j -= 1
            # 此时left位置上放置待插入的数字
        array[left] = temp
    return array


# 希尔排序
def shell_insert_sort(array):
    gap = int(len(array) / 2)
    while gap >= 1:
        for i in range(gap, len(array)):
            temp = array[i]
            j = i
            while j >= gap and array[j - gap] > temp:
                array[j] = array[j - gap]
                j -= gap
            array[j] = temp
        gap = int(gap / 2)
    return array


arr = [3, 5, 4, 9, 8, 7]
# print(insert_sort(arr))
# print(half_insert_sort(arr))
print(shell_insert_sort(arr))
